package mashibing.sort;

/**
 * 插入排序
 */
public class InsertionSort {
    public static int[] sort(int arr[]){
        if (arr == null || arr.length <2){
            return arr;
        }
        // 0 ~ 0 搞定
        // 0 ~ 1
        // 0 ~ 2
        // 0 ~ 3
        for (int i = 1; i < arr.length; i++) {
            for (int j = i - 1;j >= 0 && arr[j] > arr[j+1]; j--) {
                swap(arr, j, j+1);
            }
        }

        return arr;
    }

    //i和j是一个位置的话会出错
    private static void swap(int[] arr, int i, int j) {
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        int[] arr = {34, 56, 76, 45, 24, 78, 24, 61};
        Print.print(arr);
        int[] sortArr = sort(arr);
        Print.print(sortArr);
        long end = System.currentTimeMillis();
        System.out.println("花费时间是:"+(end-start)+"ms");
    }

    //mid = (L + R) / 2
    //mid = L + ((R - L) >> 1)
}
